﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _4Gewinnt
{

    public class MiniMax
    {

        // The colors of MIN and MAX
        private GameColor MAX;
        private GameColor MIN;

        // This board stores the various game situtations which appear while traversing the miniMax tree.
        public RedoBoard miniMaxBoard;

        public MiniMax(GameColor max, GameColor min)
        {
            this.MAX = max;
            this.MIN = min;
        }

        /// <summary>
        /// Starts the MiniMax algorithm
        /// </summary>
        /// <param name="board">The current game state from which to start the search</param>
        /// <param name="depth">The desired depth</param>
        /// <returns>The column where to put the next coin</returns>
        public int minimax(RedoBoard board, int depth)
        {
            miniMaxBoard = board.Clone();

            Node root = new Node(-1, MAX, MIN);

            // Alpha-Beta pruning variables, initialized with highes/smalles values
            int alpha = int.MinValue;
            int beta = int.MaxValue;
            // The highest score
            int score = int.MinValue;
            // The column where we put our next coin.
            int column = 0;

            foreach (Node child in root.getChildren(miniMaxBoard))
            {
                int tmp = this.min(child, depth, alpha, beta);
                // Check if we found a draw, which has a higher rating
                if(score <= tmp && miniMaxBoard.isLegalColumn(child.column)) {
                    score = tmp;
                    // Remember which draw to make
                    column = child.column; 
                }
            }

            return column;
        }

        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MAXs turn.
        /// </summary>
        /// <param name="node">The current node (Max node)</param>
        /// <param name="depth">The current depth, if it equals 1 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The maximum reachable score from node</returns>
        public int max(Node node, int depth, int alpha, int beta)
        {
            try
            {
                // Update game state
                miniMaxBoard.moveTo(MAX, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    return node.getScore(miniMaxBoard);
                }

                // Stores the score of the children
                int score = 0;

                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MAX is maximizing
                    score = Math.Max(alpha, this.min(child, depth - 1, alpha, beta));
                    // Check if we can prun the subtree. We can prun it, if MIN would never 
                    // choose the current state, because he found a better one.
                    if (beta < score)
                    {
                        // MIN never will enter this subtree, we can stop.
                        break;
                    }
                    // Update alpha value
                    alpha = score;
                }

                return alpha;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);

            }
        }

        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MINs turn.
        /// </summary>
        /// <param name="node">The current node (MIN node)</param>
        /// <param name="depth">The current depth, if it equals 1 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The minimum reachable score from node</returns>
        public int min(Node node, int depth, int alpha, int beta)
        {

            try
            {
                // Update game state
                miniMaxBoard.moveTo(MIN, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    return node.getScore(miniMaxBoard);
                }

                // Stores the score of the children
                int score = 0;

                // Its MINs turn
                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MIN is minimizing (bad states for MAX are good ones for MIN)
                    score = Math.Min(beta, this.max(child, depth - 1, alpha, beta));
                    // Like above we check whether we can prun the subtree
                    if (score < alpha)
                    {
                        break;
                    }
                    // Update beta value
                    beta = score;
                }

                return beta;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);
            }
        }
    }
}

